I’ve started work on implementing multiplayer support for Frogatto. We think there is great potential for multiplayer in Frogatto:

• Races: levels where players must race each other to the end
• Deathmatches: levels where players must defeat/kill each other. These will probably be done with some kind of twist, such as only able to hurt the other player by picking up objects and spitting them at them.
• Co-op play: levels where players must play together, helping each other to win.

Of course, none of this can be done until we have the foundation of a solid multiplayer experience in place, so that’s what I’m working on. The big goal is to provide an experience where the game continues to run at 50 frames per second, with little or no perception of lag.

To achieve this, the connection between two machines has to have as little latency as possible. We want to use a peer-to-peer system where each machine in a game has a direct connection to other machines. To achieve this I’ve implemented UDP Hole Punching so that even machines behind firewalls can establish peer-to-peer connections.

I think that a reasonable goal is that two machines which can get a round trip ping of 100ms or less should be able to play a smooth game of Frogatto. This means that two people who are both in North America, or two people in Europe, can probably play a game, as long as they have decent connections. A trans-Atlantic ping under 100ms is unlikely though, so, players on different continents will probably have some lag. Because of this, a secondary goal of the system will be to degrade as gracefully as possible.

So what does the architecture of multiplayer look like? There are a number of ways we could implement multiplayer: one would be to send position and state information about many of the dynamic objects in the level across the network. This could be made to work quite well, but uses a lot of bandwidth, and would be somewhat laggy. It would also be significant overhead to implement: every time we add new state changes for objects, we’d have to worry about making sure they get synchronized across the network properly.

Instead, we choose a different approach: in Frogatto we’ve worked carefully to make sure that all actions taken are deterministic based on their input. That is to say, if you play a Frogatto level multiple times and press the same buttons at exactly the same times, your play through will be exactly the same.

This means that all we have to do is send the other machines the button presses we’re making on our machine and the games will remain in-sync. Of course, sending a message will take some time, so in multiplayer we can’t quite expect a key press to be instant. Fortunately, we’ve done some testing and found that if we introduce a 60ms delay before a key stroke is recognized in Frogatto, it’s bare noticeable, and if we introduce a 40ms delay, it’s not noticeable at all.

So, in multiplayer, when a keystroke is made, the game will delay the time before it is put into effect by a small amount of time. When the game is started, the peers will do some tests to estimate their latency. Based on their latency, the keystroke delay will be determined. Hopefully the delay chosen will be as small as possible while still allowing packets to arrive in time.

It’s also very important that games start in synchronization — at the same time. If one system is ahead of the other, then the system that is behind will be less likely to get its data to the other system in time. So, when the game is started, the hand shaking process does its best to co-ordinate the systems to start the game at exactly the same time.

Now, it’s always possible that packets will get lost or arrive too late. Every frame we send a packet with the keystrokes for the current frame, but we also send the packets for previous frames. Additionally, we tell the other systems the furthest data of theirs that we have confirmed, so systems know they don’t have to send data for frames earlier than this. This takes care of redundancy.

Now, there is the problem of a machine getting to frame N, and only having keystroke data from its peer for frames up to frame N-1. When this happens, the machine simply waits to calculate and render the frame until it has the data. Hopefully the data will arrive within a few milliseconds, and we could possibly catch up with little or no problem. But sometimes it doesn’t. When this happens, the machine will lag, perhaps significantly. Then of course, it will be behind the other machine, and it’s likely the other machine will have the same problem.

Because both machines will be forced to lag, if it’s due to an intermittent network problem, hopefully the problem will correct and we’ll quickly get back to an equilibrium. Of course, sometimes there might be too many problems — late and lost packets — to continue at all, in which case we timeout and the game is terminated. Most of the time though, the game may be continued in some form.

Code to do all this has been checked into SVN, and Jetrel and I played our first multiplayer game last night. Hopefully in not too many more releases, it’ll be ready for prime time! 🙂